import heapq as pq


class edge:
    def __init__(self, v=0, w=0):
        self.v = v
        self.w = w


class node:
    def __init__(self, dis=0, u=0):
        self.dis = dis
        self.u = u

    def __lt__(self, other):
        return self.dis < other.dis


# maxn就是n的最大值（再加一点，比如加个7）
maxn = int(1e5 + 7)
G = [[] for i in range(maxn)]  # G[u]中放u与哪些点有边
dis = [0x3F3F3F3F for i in range(maxn)]


def dijkstra(n: int, s: int, G=G, dis=dis):
    q = []
    vis = [False for i in range(n + 1)]
    dis[s] = 0
    pq.heappush(q, node(0, s))
    while len(q):
        u = pq.heappop(q).u
        if vis[u]:
            continue
        vis[u] = True
        for ed in G[u]:
            v = ed.v
            w = ed.w
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                pq.heappush(q, node(dis[v], v))
